package dataStructure.chapter06_树.part1二叉树.binarysearchtree1;

import java.util.Comparator;

/**
 * @author https://gitee.com/W_Jun
 * @date 2022-02-25 15:45
 * @Description 二叉搜索树-添加方法add()的实现
 */
public class BinarySearchTree<E>{
    private int size;
    private Node<E> root;//根节点
    private Comparator<E> comparator;

    public BinarySearchTree(Comparator comparator) {
        this.comparator = comparator;
    }

    public BinarySearchTree() {
        this(null);
    }

    private static class Node<E> {
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

    /*
     * 添加元素的话，不能添加null，定义这个方法用来检查添加的element是否为空
     * */
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }

    /*
     * 返回值等于0代表e1与e2相等；大于0代表e1大于e2
     * */
    private int compare(E e1, E e2) {
        //比较器不为null。
        if (comparator != null) {
            //System.out.println("test-调用了comparator比较器");
            return comparator.compare(e1, e2);
        }
        //比较器如果是null，强制使用Comparable接口进行比较
        //System.out.println("test-实现了Comparable接口");
        return ((Comparable<E>)e1).compareTo(e2);
    }


    /**
     * 元素数量
     * */
    public int size(){
        return size;
    }

    /**
     * 是否为空
     * */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 清空
     * */
    public void clear() {
        root = null;
        size = 0;
    }

    /**
     * 添加元素
     * */
    public void add(E element) {
        elementNotNullCheck(element);
        //添加的是第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }
        //添加的不是第一个节点, 需要先找到父节点，然后在父节点的下面插入新节点
        //找到父节点
        Node<E> node = root;//创建新节点
        Node<E> parent = root;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                //新元素element比当前结点的值大，
                //就让element与当前结点的右子结点进行比较,直到当前结点的右子节点为空时跳出循环
                //这时，父节点正是要插入的新节点的父节点
                node = node.right;
            }else if (cmp < 0) {
                node = node.left;
            }else {
                node.element = element;//相等就进行值的覆盖
            }
        }

        //看看插入到父节点的哪个位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right =newNode;
        }else {
            parent.left = newNode;
        }
        size++;
    }
}
